As processing speeds of CPUs (Central Processor Units) have increased, CPU configurations have grown more complex. For example, a CPU comprises a computation unit, an instruction unit, a cache memory, a cache controller unit, and various registers. With advances in integration technology in recent years, there have been trends toward incorporation of CPUs on a single chip, and a need has arisen for faster operation speeds for each of the units in a CPU.
In a computation unit, there exist adders/subtractors, logical computation circuits, shift circuits, and similar. Of these, carry-save adder circuits, which are circuits to add partial products when performing multiplication, are used as adders. FIG. 7 explains multiplication operation; for example, in order to multiply E, consisting of Em through E0, and F, consisting of Fm through F0, E, that is, (Em˜E0), is multiplied by each of the digits of F, and addition of the multiplication results (called partial products) is performed. Here, if the multiplication result is G, then the multiplication result is obtained from the following equation.G=(Em˜E0)×F0+(Em˜E0)×F1+ . . . +(Em˜E0)×Fm 
In FIG. 7, the partial product X1 (X1m˜X10) is (Em˜E0)×F0, the partial product X2 (X2m˜X20) is (Em˜E0)×F1, and similarly thereafter, the partial product Xn (Xnm˜Xn0) is (Em˜E0)×Fm. These partial products are added to obtain the final multiplication result G.
Operation of a carry-save adder which adds these partial products is explained in FIG. 8. In FIG. 8, an example in which eight partial products X1 to X8 are added is shown. In the first stage, the carry-save adder (CSA) circuit calculates the addition results S1m to S10 for each digit and the carry bits C1m to C10 for each digit for the partial products X1 to X4, and the addition results S2m to S20 for each digit and the carry bits C2m to C20 for each digit for the partial products X5 to X8. In the second stage, the addition results S1m to S10, carry bits for each digit C1m to C10, addition results S2m to S20, and carry bits for each digit C2m to C20 are added for each digit, to obtain addition results S3m to S30 and carry bits C3m to C30 (see for example Japanese Patent Laid-open Hei No. 2-501242).
This CSA is configured by connecting 5-3 compressor circuits for each digit. FIG. 9 shows the configuration of a conventional CSA using 5-3 compressor circuits. In FIG. 9, the 5-3 compressor circuits 100-1, 100-2, 100-3 and 100-4 are connected in series. The 5-3 compressor circuit 100-2 (100-1, 100-3, 100-4) used in the CSA mainly comprises exclusive-OR circuits (EORs). That is, the exclusive OR of two signals is generated and used.
That is, in order to generate the complementary signals of the inputs (A1, A2, A3, A4), inverter gates 110, 112, 114, 116 are inserted, and pairs of pass transistors 120, 122, 124, 126 compute the EORs. That is, output of the EOR of A1 and A2 is the sum of the product of A1 and the inverse of A2 with the product of the inverse of A1 and A2, as shown in FIG. 10.
Hence the EOR circuit 122 outputs the EOR of A1 and A2, the EOR circuit 120 outputs the inverse of the EOR of A1 and A2, the EOR circuit 126 outputs the EOR of A3 and A4, and the EOR circuit 124 outputs the inverse of the EOR of A3 and A4.
Similarly, the EOR circuit 142 outputs the EOR of A1, A2, A3 and A4, and the EOR circuit 140 outputs the inverse of the EOR of A1, A2, A3 and A4; the EOR circuit 144 which receives these outputs outputs the EOR of A1, A2, A3, A4, and CI as the S (SUM). Similarly, the EOR circuit 146, which receives A1 via the inverse gates 134 and 152, the outputs of the EOR circuits 140 and 142, and CI via an inverse gate, outputs the carry result C shown in FIG. 10.
Further, the EOR circuit 148, which receives the output of EOR circuit 124, the output of EOR circuit 126, the inverse of A2 via an inverter gate 124, and the inverse of A4 via an inverter gate 116, outputs the carry-out result CO in FIG. 10 via the inverter gate 154. This carry-out CO is output as the carry-in CI of the upper-digit 5-3 compressor circuit 100-3.
In this way, the carry-out CO is the carry result to the upper digit, and the carry C is carried to the next stage (see FIG. 8). That is, this adder circuit is a five-input, three-output adder circuit.
However, in the technology of the prior art, complementary signals are required as input for EOR computation, as shown in FIG. 10, so that inverter gates must be inserted, and hence delay times are lengthened and high-speed addition operation is difficult. In particular, in a CSA which performs multiplication of partial products with a plurality of digits, as in FIG. 8, the delay time of one adder circuit accumulates, so that the addition time of partial products is lengthened.
Hence an object of this invention is to provide a 5-3 compressor circuit for a CSA to realize high-speed operation of the adder circuit when performing EOR computations, as well as a carry-save adder circuit using this 5-3 compressor circuit.
A further object of this invention is to provide a 5-3 compressor circuit for a CSA to prevent increases in the delay time necessary for generation of complementary signals for EOR computation, and a carry-save adder circuit using this 5-3 compressor circuit.
Still a further object of this invention is to provide a 5-3 compressor circuit for a CSA to prevent increases in delay time due to inverter gates for EOR computation, and a carry-save adder circuit using this 5-3 compressor circuit.